//1.
class Solution {
public:
    bool isValid(string s) {
        stack<char> temp;
        for(auto e: s){
            if(e=='(' || e=='{' || e=='[')
                temp.push(e);
            else { // if(e==')' || e=='}' || e==']')
                // 在访问栈顶前检查栈是否为空
                if(temp.empty())
                    return false;
                if((e==')' && temp.top()=='(') 
                || (e=='}' && temp.top()=='{' )
                || (e==']' && temp.top()=='[' )) {
                    temp.pop();
                } 
                else {
                    return false;
                }
            }
            
        }
        if(temp.empty()) //所有元素被比较完了,符合要求有效
            return true;
        return false;
    }
};

//2.哈希表存储
class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        if (n % 2 == 1) {
            return false;
        }

        unordered_map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        stack<char> stk;
        for (char ch: s) {
            if (pairs.count(ch)) {
                if (stk.empty() || stk.top() != pairs[ch]) {
                    return false;
                }
                stk.pop();
            }
            else {
                stk.push(ch);
            }
        }
        return stk.empty();
    }
};

